package com.likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class q23 {

    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> list = new ArrayList<>();
        for (ListNode node : lists) {
            ListNode listNode = node;
            while (listNode != null) {
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }

        quickSort(list, 0, list.size() - 1);

        ListNode ans = new ListNode(0);
        ListNode p = ans;
        for (Integer l : list) {
            ListNode node = new ListNode(l);
            p.next = node;
            p = p.next;
        }

        return ans.next;
    }

    private void quickSort(List<Integer> list, int left, int right) {
        if (left >= right) {
            return;
        }

        Integer pivot = list.get(right);
        int index = left;

        for (int i = left; i < right; i++) {
            if (list.get(i) < pivot) {
                int temp = list.get(i);
                list.set(i, list.get(index));
                list.set(index, temp);
                index++;
            }
        }

        list.set(right, list.get(index));
        list.set(index, pivot);

        quickSort(list, left, index - 1);
        quickSort(list, index + 1, right);
    }


//    private void mergeSort(List<Integer> list, int left, int right) {
//        if (left >= right) {
//            return;
//        }
//
//        int mid = (left + right) / 2;
//        mergeSort(list, left, mid);
//        mergeSort(list, mid + 1, right);
//
//        List<Integer> temp = new ArrayList<>();
//        int p = left;
//        int q = mid + 1;
//        while (p <= mid && q <= right) {
//            if (list.get(p) < list.get(q)) {
//                temp.add(list.get(p));
//                p++;
//            } else {
//                temp.add(list.get(q));
//                q++;
//            }
//        }
//
//        while (p <= mid) {
//            temp.add(list.get(p));
//            p++;
//        }
//        while (q <= right) {
//            temp.add(list.get(q));
//            q++;
//        }
//
//        for (int i = left, j = 0; i <= right; i++, j++) {
//            list.set(i, temp.get(j));
//        }
//    }
}
